package 二分查找.easy;


import java.util.HashMap;
import java.util.Map;

/**
 * 1. 问题描述
 *      一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 *      在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 * 2. 算法分析
 *      首先我们需要明确一点：总共有n+1个数字，其中数组中n个我们需要找到那个缺省的数字
 *      1. 采用HashMap
 *          我们先将数组转化为一个HashMap key为元素，value为出现的次数
 *          其次我们从0到n开始扫面如果当前元素不是map中的键。则缺省的数字就是这个
 *          算法简单，但是时间复杂度和空间复杂度都比较高，不推荐
 *
 *      2. 二分查找
 *          对于经典的二分查找，是给定一个目标元素，我们需要返回这个目标元素在数组中的位置
 *          如果不存在返回-1，但是此题并没有给出缺省的数字
 *          注意如果是两端缺省那么此时的数字差为1，如果是中间缺省了，那么数字差为2
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 找出缺省数字 {
    public static void main(String[] args) {

    }

    /**
     * 利用二分查找 将时间复杂度降低为O(logn)级别的
     * 分析代码实现：
     *      假设当前的数组为 nums = {0,1,2,3,4,5,6,7,9}  缺省的数字为 8
     *      nums的长度为 9
     *      我们设置两个指针 i = 0  j = 8, 分别指向数组的头和尾
     *      如果上述数组不缺省则为如下：
     *           完整的   {0,1,2,3,4,5,6,7,8,9}
     *           nums    {0,1,2,3,4,5,6,7,9}
     *      由于数组是有缺省的，但是仔细观察就会发现数组的结构可以分为两个部分
     *      一部分是索引和元素一致的一边，还有一侧则是不对应的，我们需要找到最
     *      右边对应的那个索引，因为下一位就是缺省元素
     *      例如 nums = {0,1,2,3,4,5,6,7,9}
     *          {0,1,2,3,4,5,6,7}  {9} 7就是我们想要找到的元素了
     *      代码与经典的二分查找是类似的，
     *          mid = i = (j+i) / 2;
     *          if(nums[mid] == mid) 说明此时最右边的索引与元素匹配的在mid的右边
     *          否则在左边
     * @param nums
     * @return
     */
    public static int missingNumber1(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] == mid) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }


    /**
     * 该算法是对下面的利用HashMap的一种优化，我们只需要通过一遍扫描，而且不需要额外的空间
     * 但是此时的最坏时间复杂度任然为O(n)
     * @param nums
     * @return
     */
    public static int missingNumber2(int[] nums) {
        int len = nums.length;
        if (len == 1) { // 边界判断 当nums中只有一个元素时
            return (nums[0] == 0) ? 1 : 0;
        }
        if (nums[0] != 0) { // 缺省头
            return 0;
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (i < len-1) {
                if (nums[i+1] - nums[i] >= 2) {
                    ans = (nums[i+1] + nums[i]) / 2; // 除去两头之外中间缺省
                    break;
                }
            } else { // 如果扫描到最后还是没有缺省的元素，则此时只有len元素缺省了(尾部的情况)
                ans = len;
            }
        }
        return ans;
    }

    /**
     * 不推荐的写法  时间复杂度和空间复杂度都比较高 都是O(n)
     * @param nums
     * @return
     */
    public static int missingNumber3(int[] nums) {
        // 1. 线性扫描
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums) {
            map.put(num,1);
        }
        int ans = 0;
        for(int i = 0; i <= nums.length; i++) {
            if(!map.containsKey(i)) {
                ans = i;
                break;
            }
        }
        return ans;
    }
}
